МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Кафедра САПР
Звіт
до лабораторної роботи №13
на тему «СПИСКИ, СТЕКИ, ЧЕРГИ, КІЛЬЦЯ
В МОВІ ПРОГРАМУВАННЯ С»
з курсу «Проблемно-орієнтовані мови програмування»
ЛЬВІВ 2011
Мета роботи
Навчитися використовувати динамічний розподіл пам’яті для роботи зі списками, чергами і кільцями.
Теоретичні відомості
Список - це набір елементів (найчастіше структурних змінних), розташованих у динамічній пам'яті й зв'язаних між собою з вказівниками на ці елементи. Спосіб зв'язку елементів, який застосовується, визначає тип списку.
Списки бувають лінійними й кільцевими, однозв'язними й двозв’язними. Елемент однозв'язного списку містить крім безпосередньо "корисної" інформації також інформацію про наступний або попередній елемент списку. Відповідно елемент двозв’язного списку містить інформацію, як про наступний, так і про попередні елементи. Останній елемент кільцевого списку містить вказівник на перший елемент списку.
Якщо список розташовується в оперативній пам'яті, то інформація для пошуку наступного об'єкта - адреса (вказівник) у пам'яті. Якщо зв'язний список зберігається у файлі на диску, то інформація про наступний елемент може включати зсув елемента від початку файлу, положення вказівника запису/зчитування файлу, ключ запису або будь-яку іншу інформацію, що дозволяє однозначно відшукати наступний елемент списку.
Черга - це список з таким способом зв'язку між елементами, при якому нові елементи додаються строго в кінець списку, а вибираються для обробки строго з початку. Принцип організації черги можна описати так: "першим прийшов - першим пішов" (FІFO - Fіrst Іn, Fіrst Out). Черга елементів може бути реалізована з використанням масивів, зв'язного списку або іншим способом. Щоб не обмежувати максимальне число елементів у черзі, найбільше доцільно її побудова у вигляді однозв'язного списку. Додавання нових елементів відбувається завжди в кінець списку (в "хвіст"). Останній елемент позначається особливим чином, наприклад поле вказівника на наступний елемент дорівнює NULL. Рекомендується при роботі із чергою використовувати два вказівники: один - на початок черги, а другий -на її кінець. Це спростить як вибір елементів із черги, так і їхнє додавання.
Стек - це список з таким способом зв'язку між елементами, при якому нові елементи додаються строго в початок списку й вибираються для обробки також строго з початку списку (за принципом "першим прийшов - останнім пішов" (FІLO - Fіrst Іn, Last Out), тобто перший занесений у стек елемент буде оброблений останнім).
Кільце - це список, елементи якого утворюють замкнуту кругову систему, тобто останній створений елемент повинен містити вказівник на перший елемент.
Списки можуть бути двoнаправленими, що дає можливість обходу списків у двох напрямках. У лінійних списків у перших елементах вказівник на попередній елемент, як правило, дорівнює нулю. У двoнаправленного кільця перший елемент вказує на останній, а останній - на перший.
Індивідуальне завдання
Написати програму для видалення будь-якого елемента зі списку.
Текст програми
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<math.h>
#include<iostream.h>
struct st
{
char chA;
struct st *next;
};
struct st head = {NULL, NULL}, *p;
void message();
void insert()
{
char c;
cout<<"Which element add? ";
cin>>c;
struct st cur;
cur.next=NULL;
p=head.next;
cur.chA=c;
for(p = &head; p->next ; p = p->next);
cur.next = p->next;
p->next = &cur;
message();
}
void del()
{
char c;
cout<<"Which element delete?";
cin>>c;
for(p = &head; p->next &&p->next->chA!=c ; p = p->next);
struct st *tmp;
tmp = p->nex...
